package com.xmg.dataStructure.search;

import java.util.ArrayList;
import java.util.List;

/**
 * 二分查找
 */
public class BinarySearch {
    public static void main(String[] args) {
       int[] arr = {1,2,45,67,99,99,99,99,100,889};
       int res = binarySearch(arr,0,arr.length,1);
        System.out.println("index = "+res);

        List list = binarySearch2(arr, 0, arr.length, 99);
        System.out.println("indexList = "+list);
    }

    public static int binarySearch(int[] arr,int left,int right,int findVal){
        if(left>right){
            return -1;
        }
        int mid = (left+right) / 2;
        if(findVal>arr[mid]){
            return binarySearch(arr,mid+1,right,findVal);
        }else if(findVal < arr[mid]){
            return binarySearch(arr,left,mid-1,findVal);
        }else{
            return mid;
        }
    }

    /**
     * 带重复数据的查找方法
     * @param arr
     * @param left
     * @param right
     * @param findVal
     * @return
     */
    public static List binarySearch2(int[] arr, int left, int right, int findVal){
        if(left>right){
            return new ArrayList();
        }
        int mid = (left+right) / 2;
        if(findVal>arr[mid]){
            return binarySearch2(arr,mid+1,right,findVal);
        }else if(findVal < arr[mid]){
            return binarySearch2(arr,left,mid-1,findVal);
        }else{
            List res = new ArrayList();

            int temp = mid-1;
            while (temp>=0 && arr[temp]==findVal){
                res.add(temp);
                temp--;
            }

            res.add(mid);

            temp = mid +1;
            while (temp<arr.length && arr[temp]==findVal){
                res.add(temp);
                temp++;
            }
            return res;
        }
    }
}
